package DoExercise.HSP_ZCY.A015_暴力递归;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 题目要求：打印一个字符串的全部子序列，包含重复和不重复
 * <p>
 * 子序列也是从左向右拿字符串，但是可以不连续
 * 从左向右的模型尝试方法
 */
public class Code02_打印字符串的全部子序列
{
    public static void main(String[] args)
    {
        String test = "abc";
        List<String> ans1 = subs(test);
        List<String> ans2 = subsNoRepeat(test);
        
        for (String str : ans1)
        {
            System.out.println(str);
        }
        System.out.println("=================");
        for (String str : ans2)
        {
            System.out.println(str);
        }
        System.out.println("=================");
    }
    
    /**
     * 打印一个字符串的全部子序列，可以出现重复字符串
     *
     * @param s
     * @return
     */
    public static List<String> subs(String s)
    {
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<>();
        process1(str, 0, ans, path);
        return ans;
    }
    
    public static void process1(char[] str, int index, List<String> ans, String path)
    {
        if (index == str.length)
        {
            ans.add(path);
            return;
        }
        //不加字符后面字符，形成的所有情况递归
        String no = path;
        process1(str, index + 1, ans, no);
        //加后面的字符，形成的所有情况递归
        String yes = path + str[index];
        process1(str, index + 1, ans, yes);
    }
    
    /**
     * 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
     *
     * @param s
     * @return
     */
    public static List<String> subsNoRepeat(String s)
    {
        char[] str = s.toCharArray();
        String path = "";
        HashSet<String> set = new HashSet<>();
        process2(str, 0, set, path);
        List<String> ans = new ArrayList<>();
        for (String cur : set)
        {
            ans.add(cur);
        }
        return ans;
    }
    
    public static void process2(char[] str, int index, HashSet<String> set, String path)
    {
        if (index == str.length)
        {
            set.add(path);//通过HashSet去重
            return;
        }
        //不要字符
        String no = path;
        process2(str, index + 1, set, no);
        //要字符
        String yes = path + str[index];
        process2(str, index + 1, set, yes);
    }
}
